|
In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network. The vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a road system, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. ==Definition== Let be a finite directed graph in which every edge has a non-negative, real-valued capacity . If , we assume that . We distinguish two vertices: a source and a sink . A flow in a flow network is a real function with the following three properties for all nodes and : ;Capacity constraints: . The flow along an edge cannot exceed its capacity. ;Skew symmetry: . The net flow from to must be the opposite of the net flow from to (see example). ;Flow conservation: , unless or . The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow. i.e. Flow conservation implies: , for each vertex The residual capacity of an edge is . This defines a residual network denoted , giving the amount of ''available'' capacity. See that there can be a path from to in the residual network, even though there is no path from to in the original network. Since flows in opposite directions cancel out, ''decreasing'' the flow from to is the same as ''increasing'' the flow from to . An augmenting path is a path in the residual network, where , , and . A network is at maximum flow if and only if there is no augmenting path in the residual network . So is constructed using graph as follows: # Vertices of = # Edges of = defined as- For each edge # If make Forward edge with capacity . # If make Backward edge with capacity . This concept is used in Ford–Fulkerson algorithm which computes the maximum flow in a flow network. Sometimes one needs to model a network with more than one source, a supersource is introduced to the graph. This consists of a vertex connected to each of the sources with edges of infinite capacity, so as to act as a global source. A similar construct for sinks is called a supersink. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「flow network」の詳細全文を読む スポンサード リンク
|